package 力扣_二分查找;

/**
 * @author zx
 * @create 2022-08-26 21:33
 */
public class 搜索插入位置_35 {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target){
                right = mid - 1;
            }
        }
        //查找结束如果没有相等值则返回left, 该值为插入位置
        return left;
    }

    /**
     * @return 看起来好理解,但是和模板偏差太大
     */
    public int searchInsert2(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        int res = -1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] == target){
                res = mid;
                break;
            }
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] >= target){
                res = mid;
                right = mid - 1;
            }
            if(left >= nums.length){//大于数组中所有元素
                return nums.length;
            }
        }
        return res;
    }
}
